/*
 * NodoInterno.cpp
 *
 *  Created on: 25/03/2010
 *      Author: Grupo Klow
 */

#include "NodoInterno.h"
#include <string.h>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>


NodoInterno::NodoInterno(unsigned int bytesCapacidad, char * bloque, Nodo::IDNodo id){
	this->iniciar(bytesCapacidad,id);
	this->Cargar(bloque);

}

NodoInterno::NodoInterno(unsigned int bytesCapacidad, Nodo::IDNodo id){
	this->iniciar(bytesCapacidad,id);
	this->Sucesores = (Nodo::IDNodo*) malloc (sizeof(Nodo::IDNodo));
	this->Sucesores[0]=0;
}

void NodoInterno::iniciar(unsigned int bytesCapacidad, Nodo::IDNodo id) {

	this->IDs = NULL;
	this->Sucesores = NULL;

	//La capacidad pasada por parametro menos el espacio destinado a guardar la cantidad
	//de elementos que tiene el nodo, el tipo de nodo y el sucesor izquierdo inicial
	this->bytesCapacidad = bytesCapacidad - sizeof(unsigned int) - sizeof(Nodo::IDNodo) - 1;
	this->bytesUtilizados = 0;

	this->cantidad_elementos = 0;
	this->id = id;
}

// Informacion de bloque de archivo a Nodo
void NodoInterno::Cargar(char * bloque) {

	unsigned int longitud;
	unsigned int actual=0;
	unsigned int i;

	// Datos de control
	actual = 1;
	longitud = sizeof(unsigned int);
	memcpy(&this->cantidad_elementos,&bloque[actual], longitud);
	actual+=longitud;

	// Incializo los arrays
	this->IDs = (Nodo::TClave*) malloc (sizeof(Nodo::TClave) * this->cantidad_elementos);
	this->Sucesores = (Nodo::IDNodo*) malloc (sizeof(Nodo::IDNodo)* (this->cantidad_elementos+1));

	// Cargo los IDS que tiene el nodo
	for (i=0; i < this->cantidad_elementos; i++) {
		longitud = this->obtenerLongitudClave(&bloque[actual]) ;
		this->IDs[i] = (char*) malloc(sizeof(char*) * longitud);
		memcpy(this->IDs[i],&bloque[actual],longitud);
		actual += longitud;
	}

	// Cargo los sucesores
	longitud = sizeof(IDNodo) * (cantidad_elementos +1);
	memcpy(this->Sucesores, &bloque[actual], longitud);
	actual+=longitud;

	this->bytesUtilizados = actual - sizeof(unsigned int) - sizeof(Nodo::IDNodo);

}
// Informacion de Nodo a bloque para escribir en archivo
void NodoInterno::Guardar(char * bloque) {

	unsigned int longitud;
	unsigned int actual=0;
	unsigned int i;

	actual= 1;

	// Copio el tipo de nodo
	bloque[0]= NODO_INTERNO;

	// Copio la cantidad de elementos que tiene
	longitud = sizeof(unsigned int);
	actual = 1;
	memcpy(&bloque[actual],&this->cantidad_elementos,longitud);

	actual+=longitud;
	// Copio los ids
	for (i=0; i < this->cantidad_elementos; i++) {
		longitud = this->obtenerLongitudClave(this->IDs[i]);
		memcpy(&bloque[actual],this->IDs[i],longitud);
		actual += longitud;
	}

	// Copio los sucesores
	longitud = sizeof(IDNodo) * (this->cantidad_elementos+1);
	memcpy(&bloque[actual],this->Sucesores,longitud);
}

void NodoInterno::agregarID(TClave id, IDNodo sucesorIzquierdo, IDNodo sucesorDerecho) {
	int pos = this->cantidad_elementos-1;

	this->IDs = (Nodo::TClave*) realloc (this->IDs, sizeof(Nodo::TClave) * (this->cantidad_elementos+1));
	this->Sucesores = (Nodo::IDNodo*) realloc (this->Sucesores, sizeof(Nodo::IDNodo) * (this->cantidad_elementos+2));

	while (pos >= 0 && this->compararClaves(this->IDs[pos],id) > 0) {
		this->IDs[pos+1] = this->IDs[pos];
		this->Sucesores[pos+2]=this->Sucesores[pos+1];
		pos--;
	}

	//A los bytes utilizados se le suma la longitud de la clave y la referencia al sucesor
	this->bytesUtilizados += this->obtenerLongitudClave(id) + sizeof(Nodo::IDNodo);

	this->IDs[pos+1] = this->clonarClave(id);

	if (sucesorIzquierdo != 0) {
		this->Sucesores[pos+1] = sucesorIzquierdo;
	}
	this->Sucesores[pos+2] = sucesorDerecho;

	this->cantidad_elementos++;
}
/*
 * Teniendo en cuenta los pesos de las claves busca el centro
 * cuyo peso no sera tenido en cuenta en el balanceo
 */
Nodo::TClave NodoInterno::buscarMedio(Nodo::TClave clave) {
	unsigned int bytesAgregar = this->obtenerLongitudClave(clave) +  sizeof(Nodo::IDNodo);
	unsigned int peso = 0;
	unsigned int pesoAnterior = 0;
	unsigned int i = 0;
	unsigned int posClave= this->cantidad_elementos+1; //Este valor sirve para indicar que la clave no fue puesta
	unsigned int pesoTotal = this->bytesUtilizados+bytesAgregar;
	unsigned int pesoMedio = pesoTotal / 2;
	unsigned int pesoA = 0;
	unsigned int pesoB = 0;
	unsigned int centroA = 0;
	unsigned int centroB = 0;
	TClave centro;

	 int p1 = 0;
	 int p2 = 0;

	while (peso < pesoMedio && this->compararClaves(this->IDs[i],clave) < 0 && i < this->cantidad_elementos) {
			pesoAnterior=peso;
			peso+= this->obtenerLongitudClave(this->IDs[i]) + sizeof(Nodo::IDNodo);
			i++;
	}

	if (peso < pesoMedio) {
		pesoAnterior = peso;
		peso+= this->obtenerLongitudClave(clave) + sizeof(Nodo::IDNodo);
		posClave = i;
	}

	while (peso < pesoMedio) {
		i++;
		pesoAnterior = peso;
		peso+=  this->obtenerLongitudClave(this->IDs[i-1]) + sizeof(Nodo::IDNodo);
	}


	//PesoA corresponde a la distribucion anterior
	//PesoB corresponde a la ultima distribucion

		//Combiene la distribucion anterior a la ultima
		//El ultimo que se agrego fue la clave y estaba de mas
		if (i==posClave) {
			//Elcentro es la clave
			pesoA = this->obtenerLongitudClave(clave);
			centroA = this->cantidad_elementos;
		} else {
			pesoA = this->obtenerLongitudClave(this->IDs[i-1]);
			centroA = i-1;
		}
		pesoA+= sizeof(Nodo::IDNodo);

		//La clave no llego a ponerse. Puede ser el centro. Puede ser el ultimo elemento o no
		if (posClave == this->cantidad_elementos+1 && this->compararClaves(this->IDs[i-1],clave) < 0 && (i == this->cantidad_elementos || strcmp(this->IDs[i],clave) > 0)) {
			pesoB = this->obtenerLongitudClave(clave);
			centroB = this->cantidad_elementos;
		} else {
			pesoB = this->obtenerLongitudClave(this->IDs[i]);
			centroB = i;
		}
		pesoB+= sizeof(Nodo::IDNodo);

		p1 = peso - (pesoTotal - peso - pesoB);
		p2 = (pesoTotal - pesoA - pesoAnterior) - pesoAnterior;

		if (p1 > p2) {
			if (centroA == this->cantidad_elementos) {
				centro =  clave;
			} else {
				centro = this->IDs[centroA];
			}
		} else {
			if (centroB == this->cantidad_elementos) {
				centro = clave;
			} else {
				centro = this->IDs[centroB];
			}
		}

	return this->clonarClave(centro);

}
Nodo::TClave NodoInterno::partir(NodoInterno * nodo, TClave clave, IDNodo sucesorDerecho) {

	TClave centro = this->buscarMedio(clave);

	int i = this->cantidad_elementos-1;
	//Paso los elementos a la otra mitad
	while (  this->compararClaves(this->IDs[i],centro) > 0) {
		nodo->agregarID(this->IDs[i],this->Sucesores[i],this->Sucesores[i+1]);
		this->eliminarElemento(i);
		i--;
	}
	//El centro es igual a la clave
	if ( this->compararClaves(clave,centro) ==0 ) {
		nodo->setSucesor(sucesorDerecho,0);
	} else {
		this->eliminarElemento(i);
		//El centro no es la clave. La debo ingresar al nodo izq o al der
		if (this->compararClaves(clave,centro) < 0) {
			this->agregarID(clave,0,sucesorDerecho);
		} else {
			nodo->agregarID(clave,0,sucesorDerecho);
		}
	}

	//Devuelvo el centro, que no fue puesto en ninguna de las dos partes
	return centro;
}

Nodo::IDNodo NodoInterno::buscarSucesor(TClave id) {
	unsigned int pos=0;

	while (pos < this->cantidad_elementos && this->compararClaves(this->IDs[pos],id) <= 0) {
			pos++;
	}
	return this->Sucesores[pos];
}

Nodo::IDNodo NodoInterno::buscarPosSucesor(TClave id) {

	unsigned int pos=0;
	//TODO funcion de comparacion
	while (pos < this->cantidad_elementos && this->compararClaves(this->IDs[pos],id) <= 0) {
			pos++;
	}
	return pos;
}

Nodo::TipoNodo NodoInterno::getTipo() {
	return Nodo::NODO_INTERNO;
}

Nodo::IDNodo NodoInterno::getID() {
	return this->id;
}

unsigned short int NodoInterno::getCantidadElementos() {
	return this->cantidad_elementos;
}

Nodo::TClave NodoInterno::getClave(unsigned short int posicion ){
	if (posicion < this->cantidad_elementos) {
	return this->clonarClave(this->IDs[posicion]);
	}
	return 0;
}

Nodo::IDNodo NodoInterno::getSucesor(unsigned short int posicion) {
	return this->Sucesores[posicion];
}

unsigned int NodoInterno::getPorcentajeOcupacional() {
	return (this->bytesUtilizados *100 / this->bytesCapacidad);
}

bool NodoInterno::isUnderflow(){
	// Se considera un nodo en underflow si la capacidad utilizada del nodo	es menor a un (50-T)% de su tamanio
	return (this->bytesUtilizados < ( this->bytesCapacidad * (0.5 - (PORCENTAJE_MAX_ELEM*0.01) ) ) );
}

bool NodoInterno::isOverflow(Nodo::TClave clave){
	//Si se le mete esta clave y un sucesor supera el espacio permitido?
	return ( (this->bytesUtilizados+ this->obtenerLongitudClave(clave) + sizeof(Nodo::IDNodo)) > this->bytesCapacidad);

}
/*
 * Retorna verdadero si se puede cambiar la clave que hay en la posicion 'pos'
 * por la pasada por parametro sin que se produzca overflow
 */
bool NodoInterno::posibleCambioClave(Nodo::TClave clave, unsigned short int pos) {

	unsigned int bytesUsados = this->bytesUtilizados;

	bytesUsados= bytesUsados + this->obtenerLongitudClave(clave) - this->obtenerLongitudClave(this->IDs[pos]);

	return (bytesUsados <= this->bytesCapacidad);
}

bool NodoInterno::cede_primero(){

	//Si se le quita la primer clave (y un sucesor) me queda en overflow?
	unsigned int tamanio = this->obtenerLongitudClave(this->IDs[0]) + sizeof(Nodo::IDNodo);
	return (this->bytesUtilizados - tamanio >= ( this->bytesCapacidad * (0.5 - (PORCENTAJE_MAX_ELEM*0.01) ) ) );
}

bool NodoInterno::cede_ultimo(){
	//Si se le quita la primer clave (y un sucesor) me queda en overflow?
	unsigned int tamanio = this->obtenerLongitudClave(this->IDs[this->cantidad_elementos-1]) + sizeof(Nodo::IDNodo);
	return (this->bytesUtilizados - tamanio >= ( this->bytesCapacidad * (0.5 - (PORCENTAJE_MAX_ELEM*0.01) ) ) );

}

void NodoInterno::concatenar(NodoInterno * origen) {
	unsigned int cantidad_a_Pasar;
	unsigned int offset;


	cantidad_a_Pasar = origen->cantidad_elementos;
	offset = this->cantidad_elementos;

	//Se pide memoria para los nuevos elementos
	this->IDs = (Nodo::TClave*) realloc (this->IDs, sizeof(Nodo::TClave) * (this->cantidad_elementos+cantidad_a_Pasar));
	this->Sucesores = (Nodo::IDNodo*) realloc (this->Sucesores, sizeof(Nodo::IDNodo) * (this->cantidad_elementos+cantidad_a_Pasar+1));

	//agrego los elementos del nodo sucesor al nodo_0
	while (cantidad_a_Pasar > 0) {
		this->Sucesores[offset + cantidad_a_Pasar] = origen->Sucesores[cantidad_a_Pasar];
		cantidad_a_Pasar--;
		this->IDs[offset + cantidad_a_Pasar]= origen->IDs[cantidad_a_Pasar];

	}
	this->Sucesores[offset] = origen->Sucesores[0];

	this->cantidad_elementos+= origen->cantidad_elementos;
	this->bytesUtilizados+= origen->bytesUtilizados;

	origen->cantidad_elementos = 0;
	origen->bytesUtilizados=0;
}

void NodoInterno::eliminarPrimerSeparador() {
	//muevo los datos
	unsigned int pos = 0;

	//decremento la cant de elementos
	this->cantidad_elementos--;
	//Se actualizan los bytes utilizados
	this->bytesUtilizados = this->bytesUtilizados - this->obtenerLongitudClave(this->IDs[0]) - sizeof(Nodo::IDNodo);
	//libero la clave
	free(this->IDs[0]);
	//Corro los elementos una posicion
	while(pos < this->cantidad_elementos){
		this->Sucesores[pos] = this->Sucesores[pos+1];
		this->IDs[pos] = this->IDs[pos+1];
		pos++;
	}
	this->Sucesores[pos] = this->Sucesores[pos+1];

	//re dimensiono la cantidad de elementos
	this->IDs = (Nodo::TClave*) realloc (this->IDs, sizeof(Nodo::TClave) * (this->cantidad_elementos));
	this->Sucesores = (Nodo::IDNodo*) realloc (this->Sucesores, sizeof(Nodo::IDNodo) * (this->cantidad_elementos+1));
}

void NodoInterno::eliminarElemento(unsigned short int pos){

	//decremento la cant de elementos
	cantidad_elementos--;

	//Se actualizan los bytes utilizados
	this->bytesUtilizados = this->bytesUtilizados - this->obtenerLongitudClave(this->IDs[pos]) - sizeof(Nodo::IDNodo);
	//libero la clave
	free(this->IDs[pos]);

	//muevo los datos
	while(pos < this->cantidad_elementos){
		this->IDs[pos] = this->IDs[pos+1];
		this->Sucesores[pos+1] = this->Sucesores[pos+2];
		pos++;
	}

	//re dimensiono la cantidad de elementos
	this->IDs = (Nodo::TClave*) realloc (this->IDs, sizeof(Nodo::TClave) * (this->cantidad_elementos));
	this->Sucesores = (Nodo::IDNodo*) realloc (this->Sucesores, sizeof(Nodo::IDNodo) * (this->cantidad_elementos+1));
}

void NodoInterno::setClave(Nodo::TClave clave,unsigned short int posicion){

	this->bytesUtilizados-= this->obtenerLongitudClave(this->IDs[posicion]);
	free(this->IDs[posicion]);

	this->bytesUtilizados+= this->obtenerLongitudClave(clave);
	this->IDs[posicion] = clave;
}

void NodoInterno::setSucesor(Nodo::IDNodo id, unsigned int pos){

	this->Sucesores[pos] = id;
}

void NodoInterno::setID(Nodo::IDNodo id) {
	this->id = id;
}

NodoInterno::~NodoInterno() {
	for (unsigned int i=0; i < this->cantidad_elementos;i++) {
		free(this->IDs[i]);
	}
	free(this->IDs);
	free(this->Sucesores);
}

void NodoInterno::Ver() {
        unsigned int i;
        std::cout << "Cantidad de elementos: " << this->cantidad_elementos << std::endl;
        std::cout << this->bytesUtilizados << "/" << this->bytesCapacidad << std::endl;

        std::cout << "IDs: ";

        for (i = 0; i < this->cantidad_elementos; i++) {
                std::cout << this->IDs[i] << " | ";
        }

        std::cout << std::endl << "Sucesores: ";

        for (i = 0; i <= this->cantidad_elementos; i++) {
                std::cout << this->Sucesores[i] << " | ";
        }

        std::cout << std::endl;
}

unsigned int NodoInterno::obtenerLongitudClave(Nodo::TClave clave) {
	return strlen(clave)+1;
}
// Retorna 0 si son iguales
// Retorna > 0 si clave1 es mayor a clave2
// Retorna < 0 si clave1 es menor a clave2
short int NodoInterno::compararClaves(Nodo::TClave clave1, Nodo::TClave clave2) {
	return strcmp(clave1,clave2);
}

Nodo::TClave NodoInterno::clonarClave (Nodo::TClave clave) {
	unsigned int longitud = this->obtenerLongitudClave(clave);
	TClave aux  = (TClave) malloc(longitud);
	//funcion de copia
	memcpy(aux,clave,longitud);
	return aux;
}

